Chapter 4: Permutation and Combination

4.1 Permutation

• Multiplication rule: if one event occurs in m ways and a second event in n ways, both events occur in m × n ways. (p.121)
• The multiplication rule extends to more than two events. (p.121)
• Addition rule: for events that are not sequential and are mutually exclusive, add the number of ways (e.g. 3 motorcycles or 2 cars = 5 ways). (p.120)
• Number of permutations of n different objects = n! = n × (n − 1) × ... × 3 × 2 × 1 = ⁿP_n. (p.122)
• 1! = 1 and 0! = 1. (p.122)
• Permutation of n different objects in a circle = (n − 1)!. (p.123)
• Arrangement in a circular bracelet or necklace (clockwise = anticlockwise): (n − 1)!/2. (p.124)
• Permutation of n objects taking r at a time: ⁿP_r = n!/(n − r)!, r ≤ n. (p.125)
• Permutation of n objects taking r at a time in a circle = ⁿP_r/r. (p.125)
• For a bracelet/necklace taking r of n objects: ⁿP_r/(2r). (p.126)
• Permutation of n objects involving identical objects: P = n!/(a! b! c! ...), where a, b, c are the numbers of identical objects of each type. (p.127)

Permutations with Certain Conditions

• Objects that must be together: treat them as one unit, then multiply by the arrangements within the group. (p.128)
• Alternating arrangements and grouped arrangements are found by multiplying the arrangements of each type. (p.128)
• For odd numbers, fill the last digit first (must be an odd digit), then arrange the rest. (p.129)
• For circular seating with two people together, treat them as one unit and multiply by 2! for their interchange. (p.129)
• For numbers less than a given value (e.g. below 5 000), consider the cases for the first digit separately. (p.130)

4.2 Combination

• Permutation: order or sequence is important. Combination: order or sequence is not important. (p.132)
• Combination is a selection from a set where positions or arrangements are not important. (p.132)
• Number of combinations of r objects from n different objects: ⁿC_r = ⁿP_r/r! = n!/[r!(n − r)!]. (p.133)
• ⁿC_r is also written as (n r) and is known as the binomial coefficient. (p.133)
• ⁿC₀ = 1 and ⁿC₁ = n. (p.133)
• For combinations with conditions, deal with the conditions first, then multiply the combinations of each group. (p.135)
• "At least" conditions: add the cases separately (e.g. ⁴C₂ × ⁵C₁ + ⁴C₁ × ⁵C₂). (p.136)